import java.util.*;

/**
 * @author LKQ
 * @date 2022/6/5 9:41
 * @description 翻转链表 + 单调栈
 */
public class Solution2 {
    public static void main(String[] args) {
        ListNode t = new ListNode(2, new ListNode(1, new ListNode(5)));
        Solution2 solution = new Solution2();
        solution.nextLargerNodes(t);
    }
    int len = 0;
    public int[] nextLargerNodes(ListNode head) {
        ListNode h = reverse(head);
        Stack<Integer> stack = new Stack<>();
        int[] ans = new int[len];
        while (h != null) {
            while (!stack.isEmpty() && h.val >= stack.peek()) {
                stack.pop();
            }
            int idx = Math.max(0, --len);
            ans[idx] = stack.isEmpty() ? 0 : stack.peek();
            stack.push(h.val);
            h = h.next;
        }
        return ans;
    }
    public ListNode reverse(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        while (cur != null) {
            ListNode next = cur.next;
            len++;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}
